package com.fr.lintcode;

import org.junit.Test;

public class Q401 {

    /**
     * @param matrix: a matrix of integers
     * @param k: An integer
     * @return: the kth smallest number in the matrix
     */
    public int kthSmallest(int[][] matrix, int k) {
        // write your code here
    	if (matrix == null) {
    		return 0;
    	}
    	int n = matrix.length;
    	int m = matrix[0].length;
    	if(k > m * n) {
    		return 0;
    	}
    	int tmp = 0;
    	int []index = new int[n];
    	for(int j = 0; j < k ; j++) {
    		tmp = Integer.MAX_VALUE;
    		int line = 0;
    		for(int i = 0; i < n; i++) {
    			if(index[i] < m && matrix[i][index[i]] < tmp) {
    				tmp = matrix[i][index[i]];
    				line = i;
    			}
    		}
    		index[line] ++;
    	}
    	return tmp;
    }

    @Test
    public void testKthSmallest() {
    	int[][] matrix = {{1,2,3},{2,4,6},{3,6,9}};
//    	int[][] matrix = {{1},{2},{3}};
    	int k = 3;
    	System.out.println(kthSmallest(matrix, k));
    }

}
